package com.cwj.课程设计;

import com.cwj.lab1.QueueCy;
import com.cwj.lab1.myArrayList;
import com.cwj.lab4.查找.散列表.Hash_table;

import javax.swing.*;
import java.io.*;
import java.util.Arrays;
import java.util.Scanner;

public class Graph_Name_star {
    //边信息类
    public static class Data {
        double time;//时间
        double dis;//距离
        double money;//钱，花费

        public Data(double dis, double time, double money) {
            this.time = time;
            this.dis = dis;
            this.money = money;
        }

    }

    //邻接表中的边结点类
    public static class Edge {
        int v;//边的末结点编号
        int indVal;//边信息在其存储数组中的索引

        public Edge(int v, int val) {
            this.v = v;
            this.indVal = val;
        }
    }

    //图类型
    public static final String UNDIRECTNAME = "unDirect";//无向图类标志
    public static final String DIRECTNAME = "Direct";//有向

    public static final double INF = (double) Integer.MAX_VALUE;//不连通标志，其实也可以采用Double.POSITIVE_INFINITY即表示正无穷1.0/0
    //是否为有向图
    private String graType = null;//边类型，其取值只能为上面两个静态常量字符串
    //图名字
    private String GraphName = null;
    //其是结点名称和其编号的映射关系
    private Hash_table<String, Integer> map;
    //其是邻接表
    private myArrayList<myArrayList<Edge>> graph;
    //存储编号到结点名称的关系
    private myArrayList<String> nodeList;
    //边信息的存储数组
    private myArrayList<Data> edgeList;
    //是否为稠密图
    private Boolean isDense;

    //点数和边数
    private int V_num, E_num;

    //全源最短路径问题
    //金钱
    private boolean []isUseMoney;//即表示最小花费的结果数据是否有效
    private int[][] moneyPath;//表示路径
    private double[][] moneyLow;//表示最小花费的值
    //下面同理
    //时间
    private boolean []isUseTime;
    private int[][] timePath;
    private double[][] timeLow;
    //距离
    private boolean []isUseDis;
    private int[][] disPath;
    private double[][] disLow;
    //中转站
    private int[][] TransferPath;
    private boolean[] isUseTransfer;
    private int[][]TransferLow;

    private Graph_Name_star() {
        this.preInit();
    }

    //初始化容器，之所以实现封装是因为其后面便于维护和可读
    private void preInit() {
        map = new Hash_table<>();
        graph = new myArrayList<>();
        nodeList = new myArrayList<>();
        edgeList = new myArrayList<>();
    }

    //由文件建图的构造函数
    public Graph_Name_star(String path) throws FileNotFoundException {
        this();
        this.init(path);
        this.judgeDense();
    }

    //由图表转图数据结构的构造函数
    public Graph_Name_star(JTable table, String name) {
        this();
        this.tableToGraph(table, name);
        this.judgeDense();
    }

    /**
     * 文件建图
     * 传统邻接表建图
     *
     * @param path 文件路径
     */
    private void init(String path) throws FileNotFoundException {
//        this();
        Scanner in = new Scanner(new File(path));
        //判断是否为无向图，即是决定了后面是否将边加两次
        boolean isUndirected = Graph_Name_star.UNDIRECTNAME.equals(this.graType = in.next());
        this.GraphName = in.next();
        V_num = in.nextInt();
        int Len = in.nextInt();
        this.E_num = isUndirected ? Len * 2 : Len;
        String uStr = null, vStr = null;
        Integer u = 0, v = 0;
        double dis = 0, time = 0, money = 0;
        int ind_edge = 0;
        for (int i = 0; i < Len; i++) {
            uStr = in.next();
            vStr = in.next();
            //加点函数
            this.addNode(uStr, vStr);
            u = this.map.find(uStr);
            v = this.map.find(vStr);
            dis = in.nextDouble();
            time = in.nextDouble();
            money = in.nextDouble();
            //加边
            edgeList.addLast(new Data(dis, time, money));
            ind_edge = this.edgeList.size() - 1;
            graph.get(u).addLast(new Edge(v, ind_edge));
            if (isUndirected) {
                graph.get(v).addLast(new Edge(u, ind_edge));
            }
        }
    }

    /**
     * 表格转图的初始化函数
     *
     * @param table 表格
     * @param name  图的名字
     */
    public void tableToGraph(JTable table, String name) {
        this.graType = Graph_Name_star.DIRECTNAME;
        this.GraphName = name;
        int Len = this.E_num = table.getRowCount();
        String uStr = null, vStr = null;
        Object tem = null;
        int u = 0, v = 0;
        double dis = 0, time = 0, money = 0;
        int ind_edge = 0;
        for (int i = 0; i < Len; i++) {
            //用于表格为空的情况
            uStr = (tem = table.getValueAt(i, 0)) == null ? "***" : tem.toString();
            vStr = (tem = table.getValueAt(i, 1)) == null ? "***" : tem.toString();
            this.addNode(uStr, vStr);
            //查点
            u = this.map.find(uStr);
            v = this.map.find(vStr);
            dis = (tem = table.getValueAt(i, 2)) == null ? Integer.MAX_VALUE : Double.parseDouble(tem.toString());
            time = (tem = table.getValueAt(i, 3)) == null ? Integer.MAX_VALUE : Double.parseDouble(tem.toString());
            money = (tem = table.getValueAt(i, 4)) == null ? Integer.MAX_VALUE : Double.parseDouble(tem.toString());
            edgeList.addLast(new Data(dis, time, money));
            ind_edge = this.edgeList.size() - 1;
            graph.get(u).addLast(new Edge(v, ind_edge));
            //graph.get(v).addLast(new Edge(u, ind_edge));
        }
        this.V_num = map.size();
    }

    /**
     * 加点
     *
     * @param uStr 其中一个节点
     * @param vStr 另一个节点
     */
//即判断两个点是否已经在哈希表中，否则就加入
    private void addNode(String uStr, String vStr) {
        Integer u = null, v = null;
        if ((u = map.find(uStr)) == null) {
            nodeList.addLast(uStr);
            map.set(uStr, u = nodeList.size() - 1);
            graph.addLast(new myArrayList<>());
        }
        if ((v = map.find(vStr)) == null) {
            nodeList.addLast(vStr);
            map.set(vStr, v = nodeList.size() - 1);
            graph.addLast(new myArrayList<>());
        }
    }

    //输出图
    public void show() {
        System.out.println("起点\t终点\t距离\t\t时间\t金钱");
        myArrayList<Edge> list = null;
        Edge ee = null;
        Data data = null;
        for (int i = 0; i < this.graph.size(); i++) {
            list = this.graph.get(i);
            for (int j = 0; j < list.size(); j++) {
                ee = list.get(j);
                data = edgeList.get(ee.indVal);
                System.out.println(nodeList.get(i) + "\t" + nodeList.get(ee.v) + "\t" + data.dis + "\t" + data.time + "\t" + data.money);
            }
        }
    }

    /**
     * 其最短路径
     *
     * @param path    存储路径的数组
     * @param lowDis  最短路径的结果
     * @param suppler 其为提供器，因为决定用边的哪个属性来计算最短路径
     */
    //全源最短路径问题：Floyd算法实现
    private void Floyd(double[][] lowDis, int[][] path, mySuppler<Data, Double> suppler) {
        // =new int[V_num][V_num];
        //path=new int[V_num][V_num];
        double cost = 0;
        this.preFloyd(path, lowDis, suppler);
        for (int i = 0; i < this.V_num; i++) {
            for (int j = 0; j < this.V_num; j++) {
                for (int k = 0; k < this.V_num; k++) {
                    cost = lowDis[j][i] + lowDis[i][k];
                    if (lowDis[j][k] > cost) {
                        lowDis[j][k] = cost;
                        path[j][k] = path[i][k];
                    }
                }
            }
        }
    }

    //距离最短路
    private void disSmallPath() {
        this.disPath = new int[this.V_num][this.V_num];
        this.disLow = new double[this.V_num][this.V_num];
        this.isUseDis=new boolean[this.V_num];
//        this.Floyd(this.disLow, this.disPath, (e) -> e.dis);
    }

    //时间最短路
    private void timeSmallPath() {
        this.timePath = new int[this.V_num][this.V_num];
        this.timeLow = new double[this.V_num][this.V_num];
        this.isUseTime=new boolean[this.V_num];
//        this.Floyd(this.timeLow, this.timePath, (e) -> e.time);
    }

    //钱最短路
    public void moneySmallPath() {
        this.moneyPath = new int[this.V_num][this.V_num];
        this.moneyLow = new double[this.V_num][this.V_num];
        this.isUseMoney=new boolean[this.V_num];
//        this.Floyd(this.moneyLow, this.moneyPath, (e) -> e.money);
    }
private void preCalculate(int[][] path, double[][] lowDis){
    for (int i = 0; i < this.V_num; i++) {
        for (int j = 0; j < this.V_num; j++) {
            path[i][j] = -1;
            lowDis[i][j] = Graph_Name_star.INF;//(double) Integer.MAX_VALUE;
            if (i == j) lowDis[i][j] = 0;
        }
    }
}
    //为Floyd算法需要的资源进行初始化
    private void preFloyd(int[][] path, double[][] lowDis, mySuppler<Data, Double> suppler) {
        this.preCalculate(path,lowDis);
        myArrayList<Edge> list = null;
        Data data = null;
        Edge ee = null;
        for (int i = 0; i < this.graph.size(); i++) {
            list = this.graph.get(i);
            for (int j = 0; j < list.size(); j++) {
                ee = list.get(j);
                data = edgeList.get(ee.indVal);
                path[i][ee.v] =i;
                lowDis[i][ee.v] = suppler.get(data);
            }
        }
    }

    /**
     * 求最短时间路径
     *
     * @param i 起点
     * @param j 终点
     * @return 返回路径节点编号的数组
     */
    public myArrayList<Integer> getTimePath(int i, int j) {
        this.checkTime(i);
        return this.getPath(this.timePath, i, j);
    }

    //检查最短时间路径的数据是否已经准备好了
    private void checkTime(int start) {
        if (this.timePath == null || this.isUseTime==null || this.timeLow == null) {
            this.timeSmallPath();
        }
        this.CalculatePath(start,this.timePath,this.timeLow,isUseTime,(e)->e.time);
    }

    /**
     * 获得最短时间的数组
     *
     * @param i 起点
     * @param j 终点
     * @return 最短时间
     */
    public double getSmallTime(int i, int j) {
        this.checkTime(i);
        return this.timeLow[i][j];
    }

    /**
     * 下面DIS,Money同理
     */
    public myArrayList<Integer> getDisPath(int i, int j) {
        this.checkDis(i);
        return this.getPath(this.disPath, i, j);
    }

    private void checkDis(int start) {
        if (this.disPath == null || isUseDis==null || this.disLow == null) {
            this.disSmallPath();
//            this.isUseDis[start] = true;
        }
        this.CalculatePath(start,this.disPath,this.disLow,this.isUseDis,e->e.dis);
    }

    public double getSmallDis(int i, int j) {
        this.checkDis(i);
        return this.disLow[i][j];
    }

    public myArrayList<Integer> getMoneyPath(int i, int j) {
        this.checkMoney(i);
        return this.getPath(this.moneyPath, i, j);
    }

    private void checkMoney(int start) {
        if (this.moneyPath == null || this.isUseMoney==null || this.moneyLow == null) {
            this.moneySmallPath();
        }
        this.CalculatePath(start,this.moneyPath,this.moneyLow,this.isUseMoney,e->e.money);
    }

    public double getSmallMoney(int i, int j) {
        this.checkMoney(i);
        return this.moneyLow[i][j];
    }

    //统一的计算路径的函数
    private myArrayList<Integer> getPath(int[][] path, int i, int j) {
        int flag = path[i][j];
        myArrayList<Integer> list = new myArrayList<>();
        list.addLast(j);
        while (flag != -1) {
            list.addLast(flag);
            flag = path[i][flag];
        }
        list.reserve();
        return list;
    }

    //计算最少中继站路径
    public myArrayList<Integer> getTransferPath(int start, int end) {
        this.BFS(start);//运行BFS;
        myArrayList<Integer> res = new myArrayList<>();
        int flag = end;
        while (flag != -1) {
            res.addLast(flag);
            flag = this.TransferPath[start][flag];
        }
        //res.addLast(start);
        res.reserve();
        return res;
    }
    public int getSmallTransferVal(int start,int end){
        this.BFS(start);
        return this.TransferLow[start][end];
    }

    /**
     * 加上面getPath得到的路径转换为节点名称的函数
     */
    public String ArrayToPath(myArrayList<Integer> list) {
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < list.size(); i++) {
            if (i > 0) {
                sb.append("-->");
            }
            sb.append(this.nodeList.get(list.get(i)));
        }
        return sb.toString();
    }

    /**
     * 广度有效搜索
     * 解决最短路径问题
     */
    private void BFS(int start) {
        if (this.TransferPath == null) {
            this.TransferPath = new int[this.V_num][this.V_num];
            this.isUseTransfer = new boolean[this.V_num];
            this.TransferLow=new int[this.V_num][this.V_num];
            for (int i = 0; i < this.V_num; i++) {
                for (int j = 0; j < this.V_num; j++) {
                    this.TransferPath[i][j]=-1;
                    this.TransferLow[i][j]=(int)INF;
                }
            }
        }
        //查询是否已经由计算过了，如果有就直接跳过计算
        if (this.isUseTransfer[start]) {
            return;
        }
        this.isUseTransfer[start] = true;
        this.TransferLow[start][start]=0;
        boolean[] vis = new boolean[this.V_num];
        QueueCy<Integer> que = new QueueCy<>();
        que.push(start);
        vis[start] = true;
        Edge ee = null;
        int cnt=0;
        int Len=0;
        while (!que.isEmpty()) {
            Len=que.size();
            for (int k = 0; k < Len; k++) {
                int top = que.pop();
                myArrayList<Edge> list = graph.get(top);
                for (int i = 0; i < list.size(); i++) {
                    ee = list.get(i);
                    if (vis[ee.v]) {
                        continue;
                    }
                    vis[ee.v] = true;
                    que.push(ee.v);
                    this.TransferPath[start][ee.v] = top;
                    this.TransferLow[start][ee.v] = cnt;
                }
            }
            cnt+=1;//中转站的长度
        }
    }

    public void setUseMoney(int start,boolean useMoney) {
        isUseMoney[start] = useMoney;
    }

    public void setUseTime(int start,boolean useTime) {
        isUseTime[start] = useTime;
    }

    public void setUseDis(int start,boolean useDis) {
        isUseDis[start] = useDis;
    }

    public void setIsUseTransfer(int start, boolean val) {
        this.isUseTransfer[start] = val;
    }

    /**
     * 将图输出，保存成文件
     */
    public void saveGraph(String path) {
        try (BufferedWriter out = new BufferedWriter(new FileWriter(new File(path)))) {
            out.write(Graph_Name_star.DIRECTNAME);
            out.newLine();
            out.write(this.GraphName);
            out.newLine();
            out.write(this.V_num + " " + this.E_num);
            out.newLine();
            myArrayList<Edge> list = null;
            Edge ee = null;
            Data data = null;
            for (int i = 0; i < this.graph.size(); i++) {
                list = this.graph.get(i);
                for (int j = 0; j < list.size(); j++) {
                    ee = list.get(j);
                    data = edgeList.get(ee.indVal);
                    out.write(nodeList.get(i) + "\t" + nodeList.get(ee.v) + "\t" + data.dis + "\t" + data.time + "\t" + data.money);
                    out.newLine();
                }
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    class Node implements Comparable<Node> {
        double lowVal;
        int ind;

        public Node(double lowVal, int ind) {
            this.lowVal = lowVal;
            this.ind = ind;
        }

        @Override
        public int compareTo(Node o) {
            double res = 0;
            if (((res = this.lowVal - o.lowVal)) == 0) {
                return 0;
            } else if (res < 0) {
                return 1;
            } else {
                return -1;
            }
        }
    }
    private void CalculatePath(int start,int[][]path,double[][]lowDis,boolean[]isUse,mySuppler<Data,Double>suppler){
        if(isUse[start]){
            return;
        }
        if(isDense){
            this.Floyd(lowDis,path,suppler);
            Arrays.fill(isUse,true);
        }else{
            this.Dijkstra(start,path,lowDis,suppler);
            isUse[start]=true;
        }
    }
/**
 * Dijkstra算法
 * 优先队列优化
 * @param start 起始点
 * @param path 路径存储数组
 * @param lowVal 数组存储数组
 * @param suppler 边权提供器
 * */
    public void Dijkstra(int start, int[][] path, double[][] lowVal,mySuppler<Data,Double>suppler) {
//        isUse[start]=true;//对应得向量为true
        boolean[] vis = new boolean[this.V_num];
        PQueue<Node> pq = new PQueue<>();
        this.preDijkstra(start, pq, path, lowVal,suppler);
        int ind = 0;
        double low = 0;
        double tempRes = 0;
        Node nn = null;
        myArrayList<Edge> list = null;
        Edge ee = null;
        //如果优先队列不为空，那么就可以继续进行
        while(!pq.isEmpty()){
            nn=pq.pop();
//            如果最短路径已经被计算好了，那么不需要继续进行，因为优先队列在压入元素时，有时候会有节点重复，所以就需要鉴别一下
            if(vis[nn.ind]){
                continue;
            }
            ind = nn.ind;
            low = nn.lowVal;
            vis[ind] = true;
            list = this.graph.get(ind);
            for (int j = 0; j < list.size(); j++) {
                ee = list.get(j);
                if(vis[ee.v]){
                    continue;
                }
                if ((tempRes =low + suppler.get(this.edgeList.get(ee.indVal))) < lowVal[start][ee.v]) {
                    lowVal[start][ee.v] = tempRes;
                    path[start][ee.v] = ind;
                    pq.insert(new Node(tempRes, ee.v));
                }
            }
        }
    }
//在进行Dijkstra算法前需要对存储数组做的准备操作
    private void preDijkstra(int start, PQueue<Node> pq, int[][] path, double[][] lowVal,mySuppler<Data,Double>suppler) {
        //this.preCalculate(path,lowVal);
        //初始化
        for (int i = 0; i < this.V_num; i++) {
            path[start][i]=-1;
            lowVal[start][i]=Graph_Name_star.INF;
        }
        lowVal[start][start]=0;
        myArrayList<Edge> list = this.graph.get(start);
        int u = 0;
        Edge ee = null;
        //根据起始点更新存储数组
        for (int i = 0; i < list.size(); i++) {
            ee = list.get(i);
            u = ee.v;
            path[start][u] = start;
            lowVal[start][u] = suppler.get(this.edgeList.get(ee.indVal));
            pq.insert(new Node(lowVal[start][u], u));
        }
    }
/**
 * 判定是否为稠密图
 * */
private void judgeDense(){
    int num=this.V_num*(this.V_num-1);
    if(num*3/2<=this.E_num){
        this.isDense=true;
    }else{
        this.isDense=false;
    }
}
    /**
     * 得到对应的边
     */
    public myArrayList<Edge> getNode_Edge(int ind) {
        return graph.get(ind);
    }

    public Data getData(int ind) {
        return edgeList.get(ind);
    }

    public String getNodeName(int ind) {
        return this.nodeList.get(ind);
    }

    public String getGraphName() {
        return GraphName;
    }

    public void setGraphName(String graphName) {
        GraphName = graphName;
    }

    public String getGraType() {
        return graType;
    }

    public int getV_num() {
        return V_num = map.size();
    }

    public int getE_num() {
        return E_num;
    }

    public void setE_num(int e_num) {
        E_num = e_num;
    }


    //测试函数
    public static void main(String[] args) throws FileNotFoundException {
        Graph_Name_star gg = new Graph_Name_star("测试数据集/图");
        gg.show();
        gg.timeSmallPath();
        for (int i = 0; i < gg.getV_num(); i++) {
            for (int j = 0; j < gg.getV_num(); j++) {
                for (int k = 0; k < QueryPane.CHOOSEQUERY.length; k++) {
                    System.out.println("起点：" + gg.getNodeName(i) + "\t终点：" + gg.getNodeName(j) + "\t" +
                            QueryPane.CHOOSEQUERY[k] + ":" + gg.chooseValue(k, i, j) +
                            "\t路径信息：" + gg.chooseSmallPath(k, i, j));
                }

            }
        }
//        gg.getTransferPath(1,6);
//        System.out.println(gg.ArrayToPath(gg.getTransferPath(1,6)));
    }

    //测试函数
    public String chooseSmallPath(int ind, int i, int j) {
        myArrayList<Integer> list = null;
        switch (ind) {
            case 0:
                list = this.getDisPath(i, j);
                break;
            case 1:
                list = this.getTimePath(i, j);
                break;
            case 2:
                list = this.getMoneyPath(i, j);
                break;
            case 3:
                list = this.getTransferPath(i, j);
                break;
        }
        return this.ArrayToPath(list);
    }

    public double chooseValue(int ind, int i, int j) {
        double res = 0;
        switch (ind) {
            case 0:
                res = this.getSmallDis(i, j);
                break;
            case 1:
                res = this.getSmallTime(i, j);
                break;
            case 2:
                res = this.getSmallMoney(i, j);
                break;
            case 3:
                res = this.getSmallTransferVal(i,j);
                break;
        }
        return res;
    }

}
